package jzOffer;

public class Num51 {
    public int reversePairs(int[] nums) {
        return reversePairsInternal(nums,0,nums.length-1);
    }
    public int reversePairsInternal(int[] nums,int l,int r){
        if(l>=r) return 0;
        int mid=(r-l)/2+l;
        int leftNum=reversePairsInternal(nums,l,mid);
        int rightNUm=reversePairsInternal(nums,mid+1,r);
        if(nums[mid]>nums[mid+1]){
            return leftNum+rightNUm+merge(nums,l,mid,r);
        }else{
            return leftNum+rightNUm;
        }
    }
    public int merge(int[] nums,int l,int mid,int r){
        int count=0;
        int[] tmp=new int[r-l+1];
        for(int i=l;i<=r;i++){
            tmp[i-l]=nums[i];
        }

        int i=l;
        int j=mid+1;
        for(int k=l;k<=r;k++){
            if(i>mid){
                nums[k]=tmp[j-l];
                j++;
            }else if(j>r){
                nums[k]=tmp[i-l];
                i++;
            }else if(tmp[i-l]<=tmp[j-l]){
                nums[k]=tmp[i-l];
                i++;
            }else{
                nums[k]=tmp[j-l];
                count+=mid-i+1;
                j++;
            }
        }
        return count;
    }
}
